#pragma once
 
#include "utility/vector.h"

#include <string.h>

namespace l8
{

template <typename T, class P = FreeStoreAllocationPolicy> class List;

// ----------------------------------------------------------------------------
// The list is a template for very light-weight lists. We are not
// using the STL because we want full control over space and speed of
// the code. This implementation is based on code by Robert Griesemer
// and Rob Pike.
//
// The list is parameterized by the type of its elements (T) and by an
// allocation policy (P). The policy is used for allocating lists in
// the C free store or the zone; see zone.h.

// Forward defined as
// template <typename T, class P = FreeStoreAllocationPolicy> class List;
template <typename T, class P>
class List
{
public:

    explicit List(int capacity)
    { Initialize(capacity); }

    ~List()
    { DeleteData(data_); }

    void* operator new(size_t size)
    { return P::New(size); }

    void operator delete(void* p, size_t)
    { return P::Delete(p); }

    // Returns a reference to the element at index i.  This reference is
    // not safe to use after operations that can change the list's
    // backing store (eg, Add).
    inline T& operator[](int i) const
    {
        ASSERT(0 <= i && i < length_);
        return data_[i];
    }

    inline T& at(int i) const
    { return operator[](i); }

    inline T& last() const
    {
        return at(length_ - 1);
    }

    bool is_empty() const
    { return length_ == 0; }

    int length() const
    { return length_; }

    int capacity() const
    { return capacity_; }

    Vector<T> ToVector() const
    { return Vector<T>(data_, length_); }

    Vector<const T> ToConstVector() const
    { return Vector<const T>(data_, length_); }

    // Adds a copy of the given 'element' to the end of the list,
    // expanding the list if necessary.
    void Add(const T& element);

    // Add all the elements from the argument list to this list.
    void AddAll(const List<T, P>& other);

    // Added 'count' elements with the value 'value' and returns a
    // vector that allows access to the elements.  The vector is valid
    // until the next change is made to this list.
    Vector<T> AddBlock(T value, int count);

    // Removes the i'th element without deleting it even if T is a
    // pointer type; moves all elements above i "down". Returns the
    // removed element.  This function's complexity is linear in the
    // size of the list.
    T Remove(int i);

    // Removes the last element without deleting it even if T is a
    // pointer type. Returns the removed element.
    T RemoveLast() { return Remove(length_ - 1); }

    // Clears the list by setting the length to zero. Even if T is a
    // pointer type, clearing the list doesn't delete the entries.
    void Clear();

    // Drops all but the first 'pos' elements from the list.
    void Rewind(int pos);

    bool Contains(const T& elm) const;

    // Iterate through all list entries, starting at index 0.
    void Iterate(void (*callback)(T* x));

    // Sort all list entries (using QuickSort)
    void Sort(int (*cmp)(const T* x, const T* y));
    void Sort();

    void Initialize(int capacity);

private:
    T* data_;
    int capacity_;
    int length_;

    T* NewData(int n)  { return static_cast<T*>(P::New(n * sizeof(T))); }
    void DeleteData(T* data)  { P::Delete(data); }

    // Increase the capacity of a full list, and add an element.
    // List must be full already.
    void ResizeAdd(const T& element);

    // Inlined implementation of ResizeAdd, shared by inlined and
    // non-inlined versions of ResizeAdd.
    void ResizeAddInternal(const T& element);

    // Resize the list.
    void Resize(int new_capacity);

    DISALLOW_COPY_AND_ASSIGN(List);
};


// implementation

template<typename T, class P>
inline void List<T, P>::Add(const T& element)
{
    if (length_ < capacity_) {
        data_[length_++] = element;
    } else {
        List<T, P>::ResizeAdd(element);
    }
}


template<typename T, class P>
inline void List<T, P>::AddAll(const List<T, P>& other)
{
    int result_length = length_ + other.length_;
    if (capacity_ < result_length) Resize(result_length);
    for (int i = 0; i < other.length_; i++)
    {
        data_[length_ + i] = other.data_[i];
    }
    length_ = result_length;
}


// Use two layers of inlining so that the non-inlined function can
// use the same implementation as the inlined version.
template<typename T, class P>
inline void List<T, P>::ResizeAdd(const T& element)
{
    ResizeAddInternal(element);
}


template<typename T, class P>
inline void List<T, P>::ResizeAddInternal(const T& element)
{
    ASSERT(length_ >= capacity_);
    // Grow the list capacity by 50%, but make sure to let it grow
    // even when the capacity is zero (possible initial case).
    int new_capacity = 1 + capacity_ + (capacity_ >> 1);
    // Since the element reference could be an element of the list, copy
    // it out of the old backing storage before resizing.
    T temp = element;
    Resize(new_capacity);
    data_[length_++] = temp;
}


template<typename T, class P>
inline void List<T, P>::Resize(int new_capacity)
{
    T* new_data = List<T, P>::NewData(new_capacity);
    memcpy(new_data, data_, capacity_ * sizeof(T));
    List<T, P>::DeleteData(data_);
    data_ = new_data;
    capacity_ = new_capacity;
}


template<typename T, class P>
inline Vector<T> List<T, P>::AddBlock(T value, int count)
{
    int start = length_;
    for (int i = 0; i < count; i++) Add(value);
    return Vector<T>(&data_[start], count);
}


template<typename T, class P>
inline T List<T, P>::Remove(int i)
{
    T element = at(i);
    --length_;

    while (i < length_)
    {
        data_[i] = data_[i + 1];
        i++;
    }
    return element;
}


template<typename T, class P>
inline void List<T, P>::Clear()
{
    DeleteData(data_);
    Initialize(0);
}


template<typename T, class P>
inline void List<T, P>::Rewind(int pos)
{
    length_ = pos;
}


template<typename T, class P>
inline void List<T, P>::Iterate(void (*callback)(T* x))
{
    for (int i = 0; i < length_; i++)
    {
        callback(&data_[i]);
    }
}


template<typename T, class P>
inline bool List<T, P>::Contains(const T& elm) const
{
    for (int i = 0; i < length_; i++)
    {
        if (data_[i] == elm)
        {
            return true;
        }
    }

    return false;
}


template<typename T, class P>
inline void List<T, P>::Sort(int (*cmp)(const T* x, const T* y))
{
    ToVector().Sort(cmp);
#ifdef DEBUG
    for (int i = 1; i < length_; i++)
        ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
#endif
}


template<typename T, class P>
inline void List<T, P>::Sort()
{
    Sort(PointerValueCompare<T>);
}


template<typename T, class P>
inline void List<T, P>::Initialize(int capacity)
{
    ASSERT(capacity >= 0);
    data_ = (capacity > 0) ? NewData(capacity) : NULL;
    capacity_ = capacity;
    length_ = 0;
}

} // namespace l8
